package com.pan.alg.niuke.link;

/**
 * 输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
 * 如果该链表长度小于k，请返回一个长度为 0 的链表。
 *
 *
 * 数据范围：0 \leq n \leq 10^50≤n≤10
 * 5
 *  ，0 \leq a_i \leq 10^90≤a
 * i
 * ​
 *  ≤10
 * 9
 *  ，0 \leq k \leq 10^90≤k≤10
 * 9
 *
 * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 * 进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 *
 * 例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：
 *
 * 其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。
 */
public class CountBackwordsKNodes {

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        //反转一个链表
        Integer listSize = getListSize(pHead);

        if(k>listSize){
            return null;
        }
        //获取链表的第k个
        ListNode KNode = getKNode(pHead,listSize-k+1);

        return KNode;

    }

    private Integer getListSize(ListNode pHead) {
        int index=0;
        while(pHead!=null){
            index++;
            pHead=pHead.next;
        }
        return index;
    }

    public static ListNode getKNode(ListNode pHead,Integer k){
        int index=0;
        ListNode returnNode = null;
        while(pHead!=null){
            index++;
            if(index==k){
                returnNode=pHead;
                break;
            }
            pHead=pHead.next;
        }

        return returnNode;
    }
}
